package 栈与队列;

import java.util.Stack;

/**
 * 173. 二叉搜索树迭代器
 *
 * 思路：要设计一个二叉搜索树的迭代器，按中序遍历（从小到大）访问节点，并满足next()和hasNext()方法。
 * 可以采用一个栈维护中序遍历，并且栈顶元素始终是下一个最小的节点.
 *
 * 栈模拟中序遍历：
 * 使用栈来维护当前未访问的最小节点。
 * 初始化时，将根节点及其所有左子节点依次压入栈中（确保栈顶是最小节点）。
 * 每次调用 next() 时，弹出栈顶节点，并将该节点的右子树的所有左子节点压入栈中（维护下一个最小节点）。
 *
 * 操作逻辑：
 * next()：弹出栈顶节点，处理其右子树的左链，保证栈顶始终是下一个最小节点。
 * hasNext()：判断栈是否为空。
 */
public class L_173 {
    private Stack<TreeNode> stack = new Stack<>();

    /**
     * 代码说明
     * 栈初始化：构造函数中调用 pushAllLeft(root)，将根节点及其所有左子节点压入栈，确保栈顶是最小节点。
     * next()：
     * 弹出栈顶节点（当前最小）。
     * 若该节点有右子树，将右子树的所有左子节点压入栈（保证下次 next() 能访问右子树的最小节点）。
     * hasNext()：直接判断栈是否为空。
     * 时间复杂度：
     * next() 均摊时间复杂度为 O(1)，每个节点被压入和弹出一次。
     * hasNext() 时间复杂度为 O(1)。
     * 空间复杂度：O(h)，栈最多存储树的高度 h 个节点。
     * @param root
     */
    public L_173(TreeNode root) {
        putAllLeft(root); // 栈初始化时压入左链
    }

    // 将当前节点以及其所有的子节点压入栈中
    private void putAllLeft(TreeNode node){
        while(node!= null){
            stack.push(node);
            node = node.left;
        }
    }

    // 弹出栈顶节点（最小节点），并将该节点的右子树的所有左子节点压入栈中（维护下一个最小值）
    public int next() {
        TreeNode current = stack.pop();
        // 若当前节点有右子树，将右子树的所有左子节点压入栈中
        putAllLeft(current.right);
        return current.val;
    }

    public boolean hasNext() {
        return !stack.isEmpty();
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
